package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _115搜索二维矩阵
 * @description
 * @date 2023/08/15 19:34
 * <p>
 * ******************************************************
 */
public class _115搜索二维矩阵 {

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int left_bound = 0;
        int top_bound = 0;
        int right_bound = n - 1;
        int bottom_bound = m - 1;

        while (top_bound < bottom_bound) {
            int mid_row = bottom_bound - (bottom_bound - top_bound) / 2;
            int curr = matrix[mid_row][0];
            if (curr > target) {
                bottom_bound = mid_row - 1;
            } else if (curr < target) {
                top_bound = mid_row;
            } else {
                return true;
            }
        }
        while (left_bound <= right_bound) {
            int mid_col = right_bound - (right_bound - left_bound) / 2;
            int curr = matrix[top_bound][mid_col];
            if (curr > target) {

                right_bound = mid_col - 1;
            } else if (curr < target){
                left_bound = mid_col + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        _115搜索二维矩阵 s = new _115搜索二维矩阵();
        System.out.println(s.searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}}, 3));
    }

}
